#define _CRT_SECURE_NO_WARNINGS  1


class Solution {
public:
    TreeNode* build(vector<int>& preorder, vector<int>& inorder,
        int& prei, int inbegin, int inend)
    {
        if (inbegin > inend)
            return NULL;

        TreeNode* root = new TreeNode(preorder[prei]);
        int rooti = inbegin;
        while (inbegin <= inend)
        {
            if (inorder[rooti] == preorder[prei])
                break;

            rooti++;
        }
        prei++;
        //[inbegin, rooti-1]rooti[rooti+1,inend]
        root->left = build(preorder, inorder, prei, inbegin, rooti - 1);
        root->right = build(preorder, inorder, prei, rooti + 1, inend);

        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
    {
        int i = 0;
        return build(preorder, inorder, i, 0, inorder.size() - 1);

    }
};